package cn.xaut.剑指offer.m01;

import java.util.*;

public class demo04 {

    // 83. 删除排序链表中的重复元素
    public ListNode deleteDuplicates(ListNode head) {

        ListNode cur = head;
        while (cur != null && cur.next != null) {
            if (cur.val == cur.next.val) {
                cur.next = cur.next.next;
            } else
                cur = cur.next;
        }
        return head;
        
/*        Set<ListNode> set = new HashSet<>();
        ListNode p = head;
        while (p != null) {
            set.add(p);
            p = p.next;
        }
        ListNode dummyHead = new ListNode(-1);
        ListNode prev = dummyHead;
        for (ListNode node : set) {
            prev.next = node;
            prev = prev.next;
        }
        return dummyHead.next;*/
    }

    
    public ListNode deleteDuplicates2(ListNode head) {

        ListNode prev = new ListNode(-1);
        prev.next = head;
        while (prev.next != null) {
            if (prev.val == prev.next.val)
                prev.next = prev.next.next;
            else
                prev = prev.next;
        }
        return head;
    }



    // 哈希表法
    public ListNode deleteDuplicates3(ListNode head) {

        Set<Integer> set = new HashSet<>();
        ListNode p = head;
        while (p != null) {
            set.add(p.val);
            p = p.next;
        }
        List<Integer> list = new ArrayList<>(set);
        Collections.sort(list);
        ListNode dummyHead = new ListNode(-1);
        ListNode prev = dummyHead;
        for (int val : list) {
            prev.next = new ListNode(val);
            prev = prev.next;
        }

        return dummyHead.next;
    }

    public static void main(String[] args) {

        /*        for (int i = 0; i < 5; i++) 
            set.add(i);

        set.add(2);*/
        Integer[] nums = {-3, -1, 0, 0, 0, 3, 3};
        Set<Integer> set = new HashSet<>(Arrays.asList(nums));
        List<Integer> list = new ArrayList<>(set);
        Collections.sort(list);
        System.out.println(list);
    }
}